﻿// 2715 后缀数组.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <memory.h>

using namespace std;

/*
* 
* https://www.acwing.com/problem/content/submission/2717/
* 
给定一个长度为 n 的字符串，只包含大小写英文字母和数字。

将字符串中的 n 个字符的位置编号按顺序设为 1∼n。

并将该字符串的 n 个非空后缀用其起始字符在字符串中的位置编号表示。

现在要对这 n 个非空后缀进行字典序排序，并给定两个数组 SA 和 Height。

排序完成后，用 SA[i] 来记录排名为 i 的非空后缀的编号，用 Height[i] 来记录排名为 i 的非空后缀与排名为 i−1 的非空后缀的最长公共前缀的长度（1≤i≤n）。

特别的，规定 Height[1]=0。

请你求出这两个数组。

输入格式
共一行，包含一个长度为 n 的仅包含大小写英文字母或数字的字符串。

输出格式
第一行包含 n 个整数，表示 SA 数组。

第二行包含 n 个整数，表示 Height 数组。

数据范围
1≤n≤106
输入样例：
abababab
输出样例：
7 5 3 1 8 6 4 2
0 2 4 6 0 1 3 5
*/


/*
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 2000010;

int n, m;
char s[N];
int sa[N], x[N], y[N], c[N], rk[N], height[N];

void get_sa()
{
    for (int i = 1; i <= n; i ++ ) c[x[i] = s[i]] ++ ;
    for (int i = 2; i <= m; i ++ ) c[i] += c[i - 1];
    for (int i = n; i; i -- ) sa[c[x[i]] -- ] = i;
    for (int k = 1; k <= n; k <<= 1)
    {
        int num = 0;
        for (int i = n - k + 1; i <= n; i ++ ) y[ ++ num] = i;
        for (int i = 1; i <= n; i ++ )
            if (sa[i] > k)
                y[ ++ num] = sa[i] - k;
        for (int i = 1; i <= m; i ++ ) c[i] = 0;
        for (int i = 1; i <= n; i ++ ) c[x[i]] ++ ;
        for (int i = 2; i <= m; i ++ ) c[i] += c[i - 1];
        for (int i = n; i; i -- ) sa[c[x[y[i]]] -- ] = y[i], y[i] = 0;
        swap(x, y);
        x[sa[1]] = 1, num = 1;
        for (int i = 2; i <= n; i ++ )
            x[sa[i]] = (y[sa[i]] == y[sa[i - 1]] && y[sa[i] + k] == y[sa[i - 1] + k]) ? num : ++ num;
        if (num == n) break;
        m = num;
    }
}

void get_height()
{
    for (int i = 1; i <= n; i ++ ) rk[sa[i]] = i;
    for (int i = 1, k = 0; i <= n; i ++ )
    {
        if (rk[i] == 1) continue;
        if (k) k -- ;
        int j = sa[rk[i] - 1];
        while (i + k <= n && j + k <= n && s[i + k] == s[j + k]) k ++ ;
        height[rk[i]] = k;
    }
}

int main()
{
    scanf("%s", s + 1);
    n = strlen(s + 1), m = 128;
    get_sa();
    get_height();

    for (int i = 1; i <= n; i ++ ) printf("%d ", sa[i]);
    puts("");
    for (int i = 1; i <= n; i ++ ) printf("%d ", height[i]);
    puts("");
    return 0;
}


*/
 

int main() {
   
    return 0;
}
